#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    O(n) complexity (平均复杂度)
    """
    def heapify(self, A):
        # A.sort()

        self.l = len(A)
        self.A = A
        n = self.l // 2 - 1
        while n >= 0:
            self.heapify_ele(n)
            n -= 1

    def heapify_ele(self, idx):
        left  = idx * 2 + 1
        right = idx * 2 + 2

        # smallest初始化
        smallest = idx

        # 注意这里一直用smallest进行比较下去
        if left < self.l:
            if self.A[left] < self.A[smallest]:
                smallest = left

        if right < self.l:
            if self.A[right] < self.A[smallest]:
                smallest = right

        if smallest != idx:
            # print('smallest %s idx %s' %(smallest, idx))
            self.A[idx], self.A[smallest] = self.A[smallest], self.A[idx]
            self.heapify_ele(smallest)
            # print(self.A)



def main():
    print("start main")
    l = [4, 3,2,1]
    s = Solution()
    s.heapify(l)
    print(l)

if __name__ == "__main__":
    main()
